package com.mid;

/**
 * Created by Lxk on 2019/7/7.
 */
public class Solution215 {

    /**
     * 返回二分后的位置
     * @param lo
     * @param hi
     * @param nums
     * @return
     */
    private int partion(int lo,int hi,int[] nums){
        int base=nums[lo];
        int left = lo;
        int right = hi+1;
        while(true){
            while(nums[++left]>base){
                if(left==hi){
                    break;
                }
            }
            while(nums[--right]<base){
                if(right==lo){
                    break;
                }
            }
            if(left>=right){
                break;
            }
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
        }
        int temp = nums[right];
        nums[right] = nums[lo];
        nums[lo] = temp;
        return right;
    }

    public int findKthLargest(int[] nums, int k) {
        if(nums==null || k<0 || k>nums.length){
            return 0;
        }
        int lo = 0,hi = nums.length-1;
        int partion = partion(lo,hi,nums);
        while(partion!=k-1){
            if(partion>k-1){
                hi = partion-1;
            }else if(partion<k-1){
                lo = partion+1;
            }
            partion = partion(lo,hi,nums);
        }
        return nums[partion];
    }

    public static void main(String[] args) {
        int[] arr = {3,2,3,1,2,4,5,5,6};
        Solution215 solution215 = new Solution215();
        System.out.println(solution215.findKthLargest(arr,4));
    }

}
